# -*- coding: utf-8 -*-            
# @Time : 2023/2/2 23:16
# @Author  : lining
# @FileName: 组合.py
"""
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
https://leetcode.cn/problems/combinations/
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
"""
a = [1, 2, 3, 4]
result = []
def select(k, index, data):
    """
    :param k: 需要取的个数
    :param index: 当前遍历的索引
    :param data: 当前已经取出来的数
    :return:
    """
    # 边界2：已经取到足够的数,加入结果集
    if len(data) == k:
        result.append(data[:])
        return
    # 边界1：剩余数值全选上也不够k个数----剪枝
    # 执行到这一步时，还没把数据加入，所以是-index
    # 一开始是写的越界判断，改成剩余数字判执行会更高效，减少执行次数
    if len(a)-index < k-len(data):
        return
    # 根据索引取出来，加进去（1）取这个数
    data.append(a[index])
    select(k, index+1, data)
    # 删除之前选中的数
    data.pop()
    select(k, index + 1, data)


select(3, 0, [])
print(result)


